home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc789.txt < prev    next >
Text File  |  1994-08-01  |  26KB  |  884 lines

  1.  
  2.                                                           RFC 789
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.     Vulnerabilities of Network Control Protocols: An Example
  21.  
  22.  
  23.  
  24.                           Eric C. Rosen
  25.  
  26.  
  27.                   Bolt Beranek and Newman Inc.
  28.  
  29. RFC 789                              Bolt Beranek and Newman Inc.
  30.                                                     Eric C. Rosen
  31.  
  32.      This paper has appeared in the January 1981 edition  of  the
  33.  
  34. SIGSOFT  Software  Engineering Notes, and will soon appear in the
  35.  
  36. SIGCOMM Computer Communications Review.  It is  being  circulated
  37.  
  38. as  an  RFC because it is thought that it may be of interest to a
  39.  
  40. wider audience, particularly to the internet community.  It is  a
  41.  
  42. case  study  of  a  particular  kind of problem that can arise in
  43.  
  44. large distributed systems,  and  of  the  approach  used  in  the
  45.  
  46. ARPANET to deal with one such problem.
  47.  
  48.  
  49.      On  October 27, 1980, there was an unusual occurrence on the
  50.  
  51. ARPANET.  For a period of several hours, the network appeared  to
  52.  
  53. be  unusable,  due to what was later diagnosed as a high priority
  54.  
  55. software  process   running   out   of   control.    Network-wide
  56.  
  57. disturbances  are  extremely  unusual  in  the  ARPANET (none has
  58.  
  59. occurred in several years), and as a  result,  many  people  have
  60.  
  61. expressed  interest  in  learning more about the etiology of this
  62.  
  63. particular incident.  The purpose of this note is to explain what
  64.  
  65. the symptoms of the problem  were,  what  the  underlying  causes
  66.  
  67. were,  and  what  lessons  can  be  drawn.   As we shall see, the
  68.  
  69. immediate cause of the problem was  a  rather  freakish  hardware
  70.  
  71. malfunction  (which is not likely to recur) which caused a faulty
  72.  
  73. sequence of network control packets to be generated.  This faulty
  74.  
  75. sequence of control packets in turn affected the apportionment of
  76.  
  77. software resources in the IMPs, causing one of the IMP  processes
  78.  
  79. to  use  an  excessive  amount  of resources, to the detriment of
  80.  
  81. other  IMP  processes.   Restoring  the  network  to  operational
  82.  
  83.  
  84.                               - 1 -
  85.  
  86. RFC 789                              Bolt Beranek and Newman Inc.
  87.                                                     Eric C. Rosen
  88.  
  89. condition  was  a  relatively straightforward task.  There was no
  90.  
  91. damage other than the outage itself,  and  no  residual  problems
  92.  
  93. once  the  network  was  restored.   Nevertheless,  it  is  quite
  94.  
  95. interesting to see the way  in  which  unusual  (indeed,  unique)
  96.  
  97. circumstances  can  bring  out vulnerabilities in network control
  98.  
  99. protocols, and that shall be the focus of this paper.
  100.  
  101.  
  102.      The problem began suddenly when  we  discovered  that,  with
  103.  
  104. very few exceptions, no IMP was able to communicate reliably with
  105.  
  106. any other IMP.  Attempts to go from a TIP to a host on some other
  107.  
  108. IMP   only   brought  forth  the  "net  trouble"  error  message,
  109.  
  110. indicating that no physical path  existed  between  the  pair  of
  111.  
  112. IMPs.   Connections  which already existed were summarily broken.
  113.  
  114. A flood of phone calls to the Network Control Center  (NCC)  from
  115.  
  116. all  around  the  country  indicated  that  the  problem  was not
  117.  
  118. localized, but rather seemed to be affecting virtually every IMP.
  119.  
  120.  
  121.      As a first step towards trying to find out what the state of
  122.  
  123. the network actually was, we dialed up a number  of  TIPs  around
  124.  
  125. the  country.  What we generally found was that the TIPs were up,
  126.  
  127. but  that  their  lines  were  down.   That  is,  the  TIPs  were
  128.  
  129. communicating  properly  with the user over the dial-up line, but
  130.  
  131. no connections to other IMPs were possible.
  132.  
  133.  
  134.      We tried manually restarting a number of IMPs which  are  in
  135.  
  136. our own building (after taking dumps, of course).  This procedure
  137.  
  138. initializes  all  of  the IMPs' dynamic data structures, and will
  139.  
  140.  
  141.                               - 2 -
  142.  
  143. RFC 789                              Bolt Beranek and Newman Inc.
  144.                                                     Eric C. Rosen
  145.  
  146. often clear up problems which arise when, as sometimes happens in
  147.  
  148. most complex software systems, the IMPs'  software  gets  into  a
  149.  
  150. "funny"  state.   The IMPs which were restarted worked well until
  151.  
  152. they were connected to the rest of  the  net,  after  which  they
  153.  
  154. exhibited  the same complex of symptoms as the IMPs which had not
  155.  
  156. been restarted.
  157.  
  158.  
  159.      From the facts so far presented, we  were  able  to  draw  a
  160.  
  161. number  of  conclusions.   Any  problem  which  affects  all IMPs
  162.  
  163. throughout the network is usually a routing problem.   Restarting
  164.  
  165. an  IMP  re-initializes  the routing data structures, so the fact
  166.  
  167. that restarting an IMP did not alleviate the problem in that  IMP
  168.  
  169. suggested  that  the problem was due to one or more "bad" routing
  170.  
  171. updates circulating in the network.  IMPs  which  were  restarted
  172.  
  173. would  just receive the bad updates from those of their neighbors
  174.  
  175. which were not restarted.  The fact that IMPs  seemed  unable  to
  176.  
  177. keep  their lines up was also a significant clue as to the nature
  178.  
  179. of the problem.  Each  pair  of  neighboring  IMPs  runs  a  line
  180.  
  181. up/down protocol to determine whether the line connecting them is
  182.  
  183. of  sufficient  quality  to be put into operation.  This protocol
  184.  
  185. involves the sending of HELLO and I-HEARD-YOU messages.  We  have
  186.  
  187. noted  in  the  past that under conditions of extremely heavy CPU
  188.  
  189. utilization, so many buffers can pile up waiting to be served  by
  190.  
  191. the  bottleneck  CPU process, that the IMPs are unable to acquire
  192.  
  193. the  buffers  needed  for  receiving  the  HELLO  or  I-HEARD-YOU
  194.  
  195. messages.  If a condition like this lasts for any length of time,
  196.  
  197.  
  198.                               - 3 -
  199.  
  200. RFC 789                              Bolt Beranek and Newman Inc.
  201.                                                     Eric C. Rosen
  202.  
  203. the  IMPs  may  not be able to run the line up/down protocol, and
  204.  
  205. lines will be declared down by the IMPs' software.  On the  basis
  206.  
  207. of  all  these  facts,  our  tentative  conclusion  was that some
  208.  
  209. malformed update was causing the routing process in the  IMPs  to
  210.  
  211. use  an excessive amount of CPU time, possibly even to be running
  212.  
  213. in an infinite loop.  (This would be  quite  a  surprise  though,
  214.  
  215. since  we  tried very hard to protect ourselves against malformed
  216.  
  217. updates when we designed the routing process.)  As we shall  see,
  218.  
  219. this  tentative  conclusion, although on the right track, was not
  220.  
  221. quite correct, and the actual situation turned  out  to  be  much
  222.  
  223. more complex.
  224.  
  225.  
  226.      When we examined core dumps from several IMPs, we noted that
  227.  
  228. most,  in  some cases all, of the IMPs' buffers contained routing
  229.  
  230. updates  waiting  to  be  processed.   Before   describing   this
  231.  
  232. situation further, it is necessary to explain some of the details
  233.  
  234. of  the  routing  algorithm's  updating  scheme.   (The following
  235.  
  236. explanation will of course be very brief and incomplete.  Readers
  237.  
  238. with a greater  level  of  interest  are  urged  to  consult  the
  239.  
  240. references.)  Every so often, each IMP generates a routing update
  241.  
  242. indicating  which  other  IMPs  are  its immediate neighbors over
  243.  
  244. operational  lines,  and  the  average   per-packet   delay   (in
  245.  
  246. milliseconds)  over that line.  Every IMP is required to generate
  247.  
  248. such an update at least once per minute, and no IMP is  permitted
  249.  
  250. to  generate  more than a dozen such updates over the course of a
  251.  
  252. minute.  Each  update  has  a  6-bit  sequence  number  which  is
  253.  
  254.  
  255.                               - 4 -
  256.  
  257. RFC 789                              Bolt Beranek and Newman Inc.
  258.                                                     Eric C. Rosen
  259.  
  260. advanced by 1 (modulo 64) for each successive update generated by
  261.  
  262. a  particular IMP.  If two updates generated by the same IMP have
  263.  
  264. sequence numbers n and m, update n  is  considered  to  be  LATER
  265.  
  266. (i.e.,  more recently generated) than update m if and only if one
  267.  
  268. of the following two conditions hold:
  269.  
  270.  
  271.  
  272.          (a) n > m, and n - m <= 32
  273.  
  274.          (b) n < m, and m - n > 32
  275.  
  276.  
  277. (where the comparisons and subtractions treat n and m as unsigned
  278.  
  279. 6-bit numbers, with  no  modulus).   When  an  IMP  generates  an
  280.  
  281. update,  it sends a copy of the update to each neighbor.  When an
  282.  
  283. IMP A receives an update u1 which was generated  by  a  different
  284.  
  285. IMP  B,  it  first  compares  the  sequence number of u1 with the
  286.  
  287. sequence number of the last update, u2, that it accepted from  B.
  288.  
  289. If  this  comparison  indicates  that  u2 is LATER than u1, u1 is
  290.  
  291. simply discarded.  If, on the other hand, u1 appears  to  be  the
  292.  
  293. LATER  update, IMP A will send u1 to all its neighbors (including
  294.  
  295. the one from which it was received).  The sequence number  of  u1
  296.  
  297. will be retained in A's tables as the LATEST received update from
  298.  
  299. B.   Of  course,  u1 is always accepted if A has seen no previous
  300.  
  301. update from B.  Note that this procedure is  designed  to  ensure
  302.  
  303. that  an  update  generated  by  a  particular  IMP  is received,
  304.  
  305. unchanged, by all other  IMPs  in  the  network,  IN  THE  PROPER
  306.  
  307. SEQUENCE.    Each routing update is broadcast (or flooded) to all
  308.  
  309. IMPs, not just to immediate neighbors of the IMP which  generated
  310.  
  311.  
  312.                               - 5 -
  313.  
  314. RFC 789                              Bolt Beranek and Newman Inc.
  315.                                                     Eric C. Rosen
  316.  
  317. the update (as in some other routing algorithms).  The purpose of
  318.  
  319. the  sequence numbers is to ensure that all IMPs will agree as to
  320.  
  321. which update from a given IMP  is  the  most  recently  generated
  322.  
  323. update from that IMP.
  324.  
  325.  
  326.      For  reliability,  there  is  a  protocol for retransmitting
  327.  
  328. updates over individual links.  Let X and Y be neighboring  IMPs,
  329.  
  330. and let A be a third IMP.  Suppose X receives an update which was
  331.  
  332. generated by A, and transmits it to Y.  Now if in the next 100 ms
  333.  
  334. or  so, X does not receive from Y an update which originated at A
  335.  
  336. and whose sequence number is at least as recent as  that  of  the
  337.  
  338. update  X  sent  to  Y,  X concludes that its transmission of the
  339.  
  340. update did not get through to Y, and  that  a  retransmission  is
  341.  
  342. required.   (This  conclusion is warranted, since an update which
  343.  
  344. is  received  and  adjudged  to  be  the  most  recent  from  its
  345.  
  346. originating  IMP is sent to all neighbors, including the one from
  347.  
  348. which it was received.)  The IMPs do not keep the original update
  349.  
  350. packets  buffered  pending  retransmission.   Rather,   all   the
  351.  
  352. information  in  the  update  packet  is  kept in tables, and the
  353.  
  354. packet  is  re-created  from  the  tables  if  necessary  for   a
  355.  
  356. retransmission.
  357.  
  358.  
  359.      This  transmission  protocol  ("flooding")  distributes  the
  360.  
  361. routing updates  in a  very  rapid  and  reliable  manner.   Once
  362.  
  363. generated by an IMP, an update will almost always reach all other
  364.  
  365. IMPs  in  a time period on the order of 100 ms.  Since an IMP can
  366.  
  367. generate no more than a dozen updates per minute, and  there  are
  368.  
  369.                               - 6 -
  370.  
  371. RFC 789                              Bolt Beranek and Newman Inc.
  372.                                                     Eric C. Rosen
  373.  
  374. 64  possible sequence numbers, sequence number wrap-around is not
  375.  
  376. a problem.  There is only one exception  to  this.   Suppose  two
  377.  
  378. IMPs  A  and  B  are  out  of  communication for a period of time
  379.  
  380. because there is no physical path between them.  (This may be due
  381.  
  382. either to a network partition, or to a more  mundane  occurrence,
  383.  
  384. such  as  one  of  the  IMPs  being down.)  When communication is
  385.  
  386. re-established, A and B have no way of knowing how long they have
  387.  
  388. been out of communication, or how many times the other's sequence
  389.  
  390. numbers may have wrapped around.  Comparing the  sequence  number
  391.  
  392. of  a newly received update with the sequence number of an update
  393.  
  394. received before the outage may give an incorrect result.  To deal
  395.  
  396. with this problem, the following scheme is adopted.   Let  t0  be
  397.  
  398. the time at which IMP A receives update number n generated by IMP
  399.  
  400. B.   Let  t1 be t0 plus 1 minute.  If by t1, A receives no update
  401.  
  402. generated by B with a LATER sequence number than n, A will accept
  403.  
  404. any update from B as being more recent than n.  So  if  two  IMPs
  405.  
  406. are  out  of  communication  for  a  period of time which is long
  407.  
  408. enough for the sequence numbers  to  have  wrapped  around,  this
  409.  
  410. procedure  ensures  that  proper  resynchronization  of  sequence
  411.  
  412. numbers is effected when communication is re-established.
  413.  
  414.  
  415.      There is just one more facet of the updating  process  which
  416.  
  417. needs  to  be  discussed.   Because  of  the way the line up/down
  418.  
  419. protocol works, a line cannot be  brought  up  until  60  seconds
  420.  
  421. after  its performance becomes good enough to warrant operational
  422.  
  423. use.  (Roughly speaking, this is the time it takes  to  determine
  424.  
  425.  
  426.                               - 7 -
  427.  
  428. RFC 789                              Bolt Beranek and Newman Inc.
  429.                                                     Eric C. Rosen
  430.  
  431. that  the  line's  performance  is  good  enough.)   During  this
  432.  
  433. 60-second period, no data is sent  over  the  line,  but  routing
  434.  
  435. updates are transmitted.  Remember that every node is required to
  436.  
  437. generate  a  routing update at least once per minute.  Therefore,
  438.  
  439. this procedure ensures that if two IMPs are out of  communication
  440.  
  441. because  of  the  failure  of some line, each has the most recent
  442.  
  443. update  from   the   other   by   the   time   communication   is
  444.  
  445. re-established.
  446.  
  447.  
  448.      This  very  short  introduction  to  the routing algorithm's
  449.  
  450. updating protocol should provide enough background to enable  the
  451.  
  452. reader  to  understand  the  particular problem under discussion;
  453.  
  454. further justification and detail can be found in the  references.
  455.  
  456.  
  457.      Let  us  return now to the discussion of the network outage.
  458.  
  459. I have already mentioned that the core dumps  showed  almost  all
  460.  
  461. buffers   holding  routing  updates  which  were  waiting  to  be
  462.  
  463. processed.  Close inspection showed that  all  the  updates  were
  464.  
  465. from  a  single  IMP, IMP 50.  By a strange "coincidence," IMP 50
  466.  
  467. had been  malfunctioning  just  before  the  network-wide  outage
  468.  
  469. occurred,  and  was  off the net during the period of the outage.
  470.  
  471. Hence it was not generating any updates during the period of  the
  472.  
  473. outage.   In  addition,  IMP 29, an immediate neighbor of IMP 50,
  474.  
  475. was also suffering hardware malfunctions (in particular, dropping
  476.  
  477. bits), but was up (though somewhat flakey) while the network  was
  478.  
  479. in  bad  shape.  Furthermore, the malfunction in IMP 50 had to do
  480.  
  481. with its ability to communicate properly with the neighboring IMP
  482.  
  483.                               - 8 -
  484.  
  485. RFC 789                              Bolt Beranek and Newman Inc.
  486.                                                     Eric C. Rosen
  487.  
  488. 29.  Although we did not yet understand how it was  possible  for
  489.  
  490. so  many updates from one IMP to be extant simultaneously, we did
  491.  
  492. understand enough to be able to get the network to recover.   All
  493.  
  494. that was necessary was to patch the IMPs to disregard any updates
  495.  
  496. from  IMP  50, which after all was down anyway.  When the network
  497.  
  498. is operating normally, broadcasting a patch to all  IMPs  can  be
  499.  
  500. done  in  a  matter of minutes.  With the network operating as it
  501.  
  502. was during the period of the outage, this can take as much  as  3
  503.  
  504. or  4 hours.  (Remember that the IMPs are generally unmanned, and
  505.  
  506. that the only way of controlling them from the  NCC  is  via  the
  507.  
  508. network  itself.   This  is perfectly satisfactory when an outage
  509.  
  510. affects only a small group of IMPs, but  is  an  obvious  problem
  511.  
  512. when  the  outage  has network-wide effects.)  This procedure was
  513.  
  514. fully successful in bringing the network back up.
  515.  
  516.  
  517.      When we looked closely at the dumps, we saw  that  not  only
  518.  
  519. were  all  the updates on the queue from IMP 50, but they all had
  520.  
  521. one of three sequence numbers (either 8, 40,  or  44),  and  were
  522.  
  523. ordered        in        the        queue       as       follows:
  524.  
  525. 8, 40, 44, 8, 40, 44, 8, 40, 44, ...  Note that by the definition
  526.  
  527. of LATER, 44 is LATER than 40 (44 > 40 and 44 - 40 <= 32), 40  is
  528.  
  529. LATER  than  8  (40 > 8 and 40 - 8 <= 32), and 8 is LATER than 44
  530.  
  531. (8 < 44 and 44 - 8 > 32).  Given the presence  of  three  updates
  532.  
  533. from the same IMP with these three sequence numbers, this is what
  534.  
  535. would  be  expected.   Since each update is LATER than one of the
  536.  
  537. others, a cycle is formed which keeps the three updates  floating
  538.  
  539.  
  540.                               - 9 -
  541.  
  542. RFC 789                              Bolt Beranek and Newman Inc.
  543.                                                     Eric C. Rosen
  544.  
  545. around  the  network  indefinitely.   Thus the IMPs spend most of
  546.  
  547. their CPU time and buffer space in processing these updates.  The
  548.  
  549. problem was to figure out how these three updates could  possibly
  550.  
  551. have  existed at the same time.  After all, getting from update 8
  552.  
  553. to update 40  should  require  2  or  3  full  minutes,  plus  31
  554.  
  555. intervening  sequence  numbers.   So  how could 8 still be around
  556.  
  557. when  40  was  generated,  especially  since  no   updates   with
  558.  
  559. intervening sequence numbers were present?
  560.  
  561.  
  562.      Our  first thought was that maybe the real-time clock in IMP
  563.  
  564. 50 was running one or two orders of magnitude faster than normal,
  565.  
  566. invalidating our assumptions about the maximum number of  updates
  567.  
  568. which  could  be  generated  in  a  given  time.   An alternative
  569.  
  570. hypothesis suggested itself however when we looked at the  binary
  571.  
  572. representations of the three sequence numbers:
  573.  
  574.  
  575.           8 - 001000
  576.  
  577.          40 - 101000
  578.  
  579.          44 - 101100
  580.  
  581.  
  582. Note  that  44  has only one more bit than 40, which has only one
  583.  
  584. more bit than 8.  Furthermore, the three different  updates  were
  585.  
  586. completely  identical,  except  for their sequence numbers.  This
  587.  
  588. suggests that  there  was  really  only  one  update,  44,  whose
  589.  
  590. sequence number was twice corrupted by dropped bits.  (Of course,
  591.  
  592. it's  also  possible  that  the  "real"  update  was  8,  and was
  593.  
  594. corrupted by added bits.  However, bit-dropping has proven itself
  595.  
  596.  
  597.                              - 10 -
  598.  
  599. RFC 789                              Bolt Beranek and Newman Inc.
  600.                                                     Eric C. Rosen
  601.  
  602. to be a much  more  common  sort  of  hardware  malfunction  than
  603.  
  604. bit-adding,  although  spontaneously  dropped  bits may sometimes
  605.  
  606. come back on spontaneously.)
  607.  
  608.  
  609.      Surely, the reader will object,  there  must  be  protection
  610.  
  611. against  dropped  bits.   Yes there is protection, but apparently
  612.  
  613. not enough.  The update packets themselves are checksummed, so  a
  614.  
  615. dropped  bit  in  an update packet is readily detected.  Remember
  616.  
  617. though that if  an  update  needs  to  be  retransmitted,  it  is
  618.  
  619. recreated  from tabled information.  For maximal reliability, the
  620.  
  621. tables must  be  checksummed  also,  and  the  checksum  must  be
  622.  
  623. recomputed every time the table is accessed.  However, this would
  624.  
  625. require  either  a  large  number  of  CPU  cycles  (for frequent
  626.  
  627. checksumming of a large area of memory)  or  a  large  amount  of
  628.  
  629. memory  (to store the checksums for a lot of small areas).  Since
  630.  
  631. CPU cycles and memory are both potentially scarce resources, this
  632.  
  633. did not seem to us to  be  a  cost-effective  way  to  deal  with
  634.  
  635. problems  that  arise, say, once per year (this is the first such
  636.  
  637. problem encountered in a year and a half of running this  routing
  638.  
  639. algorithm).   Time  and  space  can  be  saved by recomputing the
  640.  
  641. checksum at  a  somewhat  slower  frequency,  but  this  is  less
  642.  
  643. reliable,  in  that it allows a certain number of dropped bits to
  644.  
  645. "fall between the cracks."  It seems likely then that one of  the
  646.  
  647. malfunctioning  IMPs  had to retransmit update 44 at least twice,
  648.  
  649. (recreating it each time from tabled information), retransmitting
  650.  
  651. it at least once with the corrupted sequence number  40,  and  at
  652.  
  653.  
  654.                              - 11 -
  655.  
  656. RFC 789                              Bolt Beranek and Newman Inc.
  657.                                                     Eric C. Rosen
  658.  
  659. least  once  with  the  corrupted  sequence number 8.  This would
  660.  
  661. cause those three sequence numbers to be extant  in  the  network
  662.  
  663. simultaneously,  even  though protocol is supposed to ensure that
  664.  
  665. this is impossible.
  666.  
  667.  
  668.      Actually, the detection of dropped bits is most  properly  a
  669.  
  670. hardware function.  The next generation of IMP hardware (the "C30
  671.  
  672. IMP")  will  be able to detect and correct all single-bit errors,
  673.  
  674. and will detect all other bit errors.  Uncorrectable  bit  errors
  675.  
  676. will  cause  the  IMP to go into its "loader/dumper."  (An IMP in
  677.  
  678. its loader/dumper is not usable for  transferring  data,  and  is
  679.  
  680. officially   in  the  "down"  state.   However,  an  IMP  in  its
  681.  
  682. loader/dumper is easily controllable from the  NCC,  and  can  be
  683.  
  684. restarted  or  reloaded  without  on-site intervention.)  Current
  685.  
  686. hardware does have parity checking (which  should  detect  single
  687.  
  688. dropped  bits),  but  this feature has had to be turned off since
  689.  
  690. (a) there are too many spurious parity "errors,"  i.e.,  most  of
  691.  
  692. the  time when the machines complain of parity errors there don't
  693.  
  694. really seem to be any, and (b) parity errors cause  the  machines
  695.  
  696. to  simply  halt, rather than go into their loader/dumpers, which
  697.  
  698. means that on-site intervention is required to restart them.
  699.  
  700.  
  701.      Pending the introduction of improved hardware, what  can  be
  702.  
  703. done  to prevent problems like this from recurring in the future?
  704.  
  705. It is easy to think of many  ways  of  avoiding  this  particular
  706.  
  707. problem,  especially  if  one does not consider the problems that
  708.  
  709. may arise from the "fixes."  For example, we  might  be  able  to
  710.  
  711.                              - 12 -
  712.  
  713. RFC 789                              Bolt Beranek and Newman Inc.
  714.                                                     Eric C. Rosen
  715.  
  716. avoid  this  sort of problem by spending a lot more CPU cycles on
  717.  
  718. checksumming, but this may be too expensive because of  the  side
  719.  
  720. effects  it  would  introduce.   (Also,  it is not clear that any
  721.  
  722. memory checksumming strategy can be totally free of "cracks.")  A
  723.  
  724. very  simple  and  conservative  fix  to  prevent this particular
  725.  
  726. problem from recurring is to modify clause (a) of the  definition
  727.  
  728. of  LATER  so  that  the  "<="  is replaced by "<" (strictly less
  729.  
  730. than).  We will implement this fix, but it cannot  be  guaranteed
  731.  
  732. that no related problems will ever arise.
  733.  
  734.  
  735.      What  is  really  needed  is  not some particular fix to the
  736.  
  737. routing algorithm, but a more general fix.  In  some  sense,  the
  738.  
  739. problem  we  saw  was  not really a routing problem.  The routing
  740.  
  741. code was working correctly, and the routes  that  were  generated
  742.  
  743. were correct and consistent.  The real problem is that a freakish
  744.  
  745. hardware  malfunction caused a high priority process to run wild,
  746.  
  747. devouring resources needed by other processes, thereby making the
  748.  
  749. network unusable.  The fact that the wild process was the routing
  750.  
  751. process is incidental.  In  designing  the  routing  process,  we
  752.  
  753. carefully  considered the amount of resource utilization it would
  754.  
  755. require.  By strictly controlling and limiting the rate at  which
  756.  
  757. updates  can  be  generated, we tried to prevent any situation in
  758.  
  759. which the routing process would make  excessive  demands  on  the
  760.  
  761. system.   As  we  have  seen  though, even our carefully designed
  762.  
  763. mechanisms were unable to protect against every possible sort  of
  764.  
  765. hardware  failure.  We need a better means of detecting that some
  766.  
  767.  
  768.                              - 13 -
  769.  
  770. RFC 789                              Bolt Beranek and Newman Inc.
  771.                                                     Eric C. Rosen
  772.  
  773. high priority process in the IMP, despite all the  safeguards  we
  774.  
  775. have  built in, is still consuming too many resources.  Once this
  776.  
  777. is  detected,  the  IMP  can  be  automatically  placed  in   its
  778.  
  779. loader/dumper.  In the case under discussion, we would have liked
  780.  
  781. to  have  all  the  IMPs  go  into  their loader/dumpers when the
  782.  
  783. problem arose.  This would have enabled us to  re-initialize  and
  784.  
  785. restart  all  the  IMPs  much more quickly.  (Although restarting
  786.  
  787. individual  IMPs  did  little  good,  restarting  all  the   IMPs
  788.  
  789. simultaneously would have cleared up the problem instantly, since
  790.  
  791. all  routing  tables  in  all  IMPs  would  have been initialized
  792.  
  793. simultaneously.)  It took us no more than an hour to  figure  out
  794.  
  795. how  to  restore  the  network;  several  additional  hours  were
  796.  
  797. required because it took so long for us to gain  control  of  the
  798.  
  799. misbehaving  IMPs  and  get  them  back  to  normal.   A built-in
  800.  
  801. software alarm system (assuming,  of  course,  that  it  was  not
  802.  
  803. subject  to  false  alarms)  might have enabled us to restore the
  804.  
  805. network more quickly, significantly reducing the duration of  the
  806.  
  807. outage.   This  is  not  to  say  that a better alarm and control
  808.  
  809. system could ever be a replacement for careful study  and  design
  810.  
  811. which   attempts   to  properly  distribute  the  utilization  of
  812.  
  813. important resources, but only that it is a necessary adjunct,  to
  814.  
  815. handle  the cases that will inevitably fall between the cracks of
  816.  
  817. even the most careful design.
  818.  
  819.  
  820.  
  821.  
  822.  
  823.  
  824.  
  825.                              - 14 -
  826.  
  827. RFC 789                              Bolt Beranek and Newman Inc.
  828.                                                     Eric C. Rosen
  829.  
  830.                            REFERENCES
  831.  
  832.  
  833.  
  834. "The New Routing Algorithm for the ARPANET," IEEE TRANSACTIONS ON
  835.  
  836. COMMUNICATIONS, May 1980, J.M. McQuillan, I. Richer, E.C.  Rosen.
  837.  
  838.  
  839. "The  Updating  Protocol  of  ARPANET's  New  Routing Algorithm,"
  840.  
  841. COMPUTER NETWORKS, February 1980, E.C. Rosen.
  842.  
  843.  
  844.  
  845.  
  846.  
  847.  
  848.  
  849.  
  850.  
  851.  
  852.  
  853.  
  854.  
  855.  
  856.  
  857.  
  858.  
  859.  
  860.  
  861.  
  862.  
  863.  
  864.  
  865.  
  866.  
  867.  
  868.  
  869.  
  870.  
  871.  
  872.  
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.                              - 15 -
  883.  
  884.